package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-05-21 16:26
 */
public class 题库_0033_搜索旋转排序数组 {

  static
  class Solution {
    public int search(int[] nums, int target) {
      if (nums == null || nums.length == 0) {
        return -1;
      }

      int left = 0;
      int right = nums.length - 1;
      while (left <= right) {
        int middle = (left + right) / 2;
        if (nums[middle] == target) {
          return middle;
        }
        if (nums[left] == target) {
          return left;
        }
        if (nums[right] == target) {
          return right;
        }

        if (nums[left] < target) {
          // target 在前半段，middle 出现的位置能有三种：后半段 (right)、前半段 target 前 (left)、前半段 target 后(right)
          if (nums[left] < nums[middle] && nums[middle] < target) {
            left = middle + 1;
          } else {
            right = middle - 1;
          }
        } else {
          // target 在后半段，middle 出现的位置能有三种：前半段 (left)、后半段 target 前 (left)、后半段 target 后(right)
          if (target < nums[middle] && nums[middle] < nums[right]) {
            right = middle - 1;
          } else {
            left = middle + 1;
          }
        }
      }
      return -1;
    }

    public int search0(int[] nums, int target) {
      if (nums == null || nums.length == 0) {
        return -1;
      }
      if (nums[0] == target) {
        return 0;
      }
      int left = 0;
      int right = nums.length - 1;
      while (left <= right) {
        int middle = (left + right) / 2;
        if (nums[middle] == target) {
          return middle;
        }

        if (nums[left] == target) {
          return left;
        }

        if (nums[left] < target) {
          // target 在前半段
          if (nums[middle] < target) {
            if (nums[middle] >= nums[left]) {
              left = middle + 1;
            } else {
              right = middle - 1;
            }
          } else {
            right = middle - 1;
          }
        } else {
          // target 在后半段
          if (nums[middle] < target) {
            left = middle + 1;
          } else {
            if (nums[middle] >= nums[left]) {
              left = middle + 1;
            } else {
              right = middle - 1;
            }
          }
        }
      }
      return -1;
    }
  }

}
